{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Construct String from Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #string #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #字符串 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: tree2str"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #根据二叉树创建字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你二叉树的根节点 <code>root</code> ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。</p>\n",
    "\n",
    "<p>空节点使用一对空括号对 <code>\"()\"</code> 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/03/cons1-tree.jpg\" style=\"width: 292px; height: 301px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,4]\n",
    "<strong>输出：</strong>\"1(2(4))(3)\"\n",
    "<strong>解释：</strong>初步转化后得到 \"1(2(4)())(3()())\" ，但省略所有不必要的空括号对后，字符串应该是\"1(2(4))(3)\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/03/cons2-tree.jpg\" style=\"width: 207px; height: 293px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,null,4]\n",
    "<strong>输出：</strong>\"1(2()(4))(3)\"\n",
    "<strong>解释：</strong>和第一个示例类似，但是无法省略第一个空括号对，否则会破坏输入与输出一一映射的关系。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目范围是 <code>[1, 10<sup>4</sup>]</code></li>\n",
    "\t<li><code>-1000 &lt;= Node.val &lt;= 1000</code></li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [construct-string-from-binary-tree](https://leetcode.cn/problems/construct-string-from-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [construct-string-from-binary-tree](https://leetcode.cn/problems/construct-string-from-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4]', '[1,2,3,null,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        stack = [root]\n",
    "        ans = \"\"\n",
    "        visited = set()\n",
    "        while stack:\n",
    "            node = stack[-1]\n",
    "            if node in visited:\n",
    "                if node != root:\n",
    "                    ans += \")\"\n",
    "                stack.pop()\n",
    "            else:\n",
    "                visited.add(node)\n",
    "                if node != root:\n",
    "                    ans += \"(\"\n",
    "                ans += str(node.val)\n",
    "                if not node.left and node.right:\n",
    "                    ans += \"()\"\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "                if node.left:\n",
    "                    stack.append(node.left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        # if root is None:\n",
    "        #     return \"\"\n",
    "        # if root.left is None and root.right is None:\n",
    "        #     return str(root.val)\n",
    "        # if root.right is None:\n",
    "        #     return f\"{root.val}({self.tree2str(root.left)})\"\n",
    "        # return f\"{root.val}({self.tree2str(root.left)})({self.tree2str(root.right)})\"\n",
    "        ans = \"\"\n",
    "        st = [root]\n",
    "        vis = set()\n",
    "        while st:\n",
    "            node = st[-1]\n",
    "            if node in vis:\n",
    "                if node != root:\n",
    "                    ans += \")\"\n",
    "                st.pop()\n",
    "            else:\n",
    "                vis.add(node)\n",
    "                if node != root:\n",
    "                    ans += \"(\"\n",
    "                ans += str(node.val)\n",
    "                if node.left is None and node.right:\n",
    "                    ans += \"()\"\n",
    "                if node.right:\n",
    "                    st.append(node.right)\n",
    "                if node.left:\n",
    "                    st.append(node.left)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "\n",
    "        if not root:\n",
    "            return ''\n",
    "\n",
    "        if not root.left and not root.right:\n",
    "            return str(root.val)\n",
    "        \n",
    "        if not root.right:\n",
    "            return str(root.val) + '('+ self.tree2str(root.left) + ')' \n",
    "\n",
    "        return str(root.val) + '('+ self.tree2str(root.left) + ')'  + '('+ self.tree2str(root.right) + ')' "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# 一刷\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        if not root:\n",
    "            return ''\n",
    "\n",
    "        res = str(root.val)  \n",
    "        if not root.left and not root.right:\n",
    "            return res\n",
    "\n",
    "        left_res = self.tree2str(root.left)\n",
    "        right_res = self.tree2str(root.right)\n",
    "\n",
    "        res += '(' + left_res + ')'\n",
    "        if right_res: \n",
    "            res += '(' + right_res + ')'\n",
    "        return res\n",
    "\n",
    "\n",
    "# 二刷 代码简化\n",
    "# class Solution:\n",
    "#     def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "#         if not root: return ''\n",
    "\n",
    "#         left_res = '({})'.format(self.tree2str(root.left))  if (root.left or root.right) else ''\n",
    "#         right_res = '({})'.format(self.tree2str(root.right))  if root.right else ''\n",
    "#         return '{}{}{}'.format(root.val, left_res, right_res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        ans = ''\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            cur = stack[-1]\n",
    "            while cur == '(' or cur ==')':\n",
    "                ans += cur\n",
    "                stack.pop()\n",
    "                cur = stack[-1] if stack else None\n",
    "            node = stack.pop() if stack else None\n",
    "            if node:\n",
    "                ans += str(node.val)\n",
    "                if node.right or node.left:\n",
    "                    if node.right:\n",
    "                        stack.append(')')\n",
    "                        stack.append(node.right)\n",
    "                        stack.append('(')\n",
    "                    stack.append(')')\n",
    "                    stack.append(node.left)\n",
    "                    stack.append('(')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        if root is None:\n",
    "            return \"\"\n",
    "        if root.left is None and root.right is None:\n",
    "            return str(root.val)\n",
    "        if root.right is None:\n",
    "            return f\"{root.val}({self.tree2str(root.left)})\"\n",
    "        return f\"{root.val}({self.tree2str(root.left)})({self.tree2str(root.right)})\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node.left and not node.right:\n",
    "                res = '('+str(node.val)+')'\n",
    "            elif not node.left:\n",
    "                res = '('+str(node.val) + '()' + dfs(node.right) +')' \n",
    "            elif not node.right:\n",
    "                res = '('+str(node.val) + dfs(node.left) +')' \n",
    "            else:\n",
    "                res = '('+str(node.val)+ dfs(node.left) + dfs(node.right) +')' \n",
    "            return res\n",
    "\n",
    "        return dfs(root)[1:-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "\n",
    "        res = []\n",
    "\n",
    "        def dfs(root: Optional[TreeNode]):\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                return\n",
    "            res.append('(')\n",
    "            res.append(str(root.val))\n",
    "            if root.left:\n",
    "                dfs(root.left)\n",
    "            elif root.right:\n",
    "                res.append('()')\n",
    "            if root.right:\n",
    "                dfs(root.right)\n",
    "            res.append(')')\n",
    "\n",
    "        dfs(root)\n",
    "        return ''.join(res[1:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        if not root:\n",
    "            return ''\n",
    "        \n",
    "        stack = [root]\n",
    "        res = ''\n",
    "        recode = set()\n",
    "\n",
    "        while stack:\n",
    "            cur = stack[-1]\n",
    "            if cur in recode:\n",
    "                if cur != root:\n",
    "                    res += ')'\n",
    "                stack.pop()\n",
    "            else:\n",
    "                recode.add(cur)\n",
    "                if cur != root:\n",
    "                    res +='('\n",
    "                res += str(cur.val)\n",
    "                if not cur.left and cur.right:\n",
    "                    res += '()'\n",
    "                if cur.right:\n",
    "                    stack.append(cur.right)\n",
    "                if cur.left:\n",
    "                    stack.append(cur.left)\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        ans = ''\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            cur = stack[-1]\n",
    "            while cur == '(' or cur ==')':\n",
    "                ans += cur\n",
    "                stack.pop()\n",
    "                cur = stack[-1] if stack else None\n",
    "            node = stack.pop() if stack else None\n",
    "            if node:\n",
    "                ans += str(node.val)\n",
    "                if node.right or node.left:\n",
    "                    if node.right:\n",
    "                        stack.append(')')\n",
    "                        stack.append(node.right)\n",
    "                        stack.append('(')\n",
    "                    stack.append(')')\n",
    "                    stack.append(node.left)\n",
    "                    stack.append('(')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def traverse(self,root:Optional[TreeNode],res):\n",
    "        if root!=None:\n",
    "            res.append('(')\n",
    "            res.append(root.val)\n",
    "            self.traverse(root.left,res)\n",
    "            if root.left is None and root.right is not None:\n",
    "                res.append('(')\n",
    "                res.append(')')\n",
    "            self.traverse(root.right,res)\n",
    "            res.append(\")\")\n",
    "            \n",
    "\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        res=[]\n",
    "        self.traverse(root,res)\n",
    "        res=res[1:-1]\n",
    "        res_str=''.join(str(i) for i in res)\n",
    "        return res_str"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        res = ''\n",
    "        stack = [root]\n",
    "        recode = set()\n",
    "\n",
    "        while stack:\n",
    "            cur = stack[-1]\n",
    "            if cur in recode:\n",
    "                if cur != root:\n",
    "                    res += ')'\n",
    "                stack.pop()\n",
    "            else:\n",
    "                recode.add(cur)\n",
    "                if cur != root:\n",
    "                    res += '('\n",
    "                res += str(cur.val)\n",
    "                if not cur.left and cur.right:\n",
    "                    res += '()'\n",
    "                if cur.right:\n",
    "                    stack.append(cur.right)\n",
    "                if cur.left:\n",
    "                    stack.append(cur.left)\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        if not root:\n",
    "            return ''\n",
    "        \n",
    "        stack = [root]\n",
    "        res = ''\n",
    "        recode = set()\n",
    "\n",
    "        while stack:\n",
    "            cur = stack[-1]\n",
    "            if cur in recode:\n",
    "                if cur != root:\n",
    "                    res += ')'\n",
    "                stack.pop()\n",
    "            else:\n",
    "                recode.add(cur)\n",
    "                if cur != root:\n",
    "                    res +='('\n",
    "                res += str(cur.val)\n",
    "                if not cur.left and cur.right:\n",
    "                    res += '()'\n",
    "                if cur.right:\n",
    "                    stack.append(cur.right)\n",
    "                if cur.left:\n",
    "                    stack.append(cur.left)\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        data = []\n",
    "\n",
    "        def collect(node: TreeNode):\n",
    "            if not node:\n",
    "                return\n",
    "            data.append(str(node.val))\n",
    "            if  node.left is not None:\n",
    "                data.append('(')\n",
    "                collect(node.left)\n",
    "                data.append(')')\n",
    "\n",
    "            if  node.right is not None:\n",
    "                if node.left is None:\n",
    "                    data.append('()')\n",
    "                data.append('(')\n",
    "                collect(node.right)\n",
    "                data.append(')')\n",
    "\n",
    "        collect(root)\n",
    "        return ''.join(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        ans = \"\"\n",
    "        st = [root]\n",
    "        vis = set()\n",
    "        while st:\n",
    "            node = st[-1]\n",
    "            if node in vis:\n",
    "                if node != root:\n",
    "                    ans += \")\"\n",
    "                st.pop()\n",
    "            else:\n",
    "                vis.add(node)\n",
    "                if node != root:\n",
    "                    ans += \"(\"\n",
    "                ans += str(node.val)\n",
    "                if node.left is None and node.right:\n",
    "                    ans += \"()\"\n",
    "                if node.right:\n",
    "                    st.append(node.right)\n",
    "                if node.left:\n",
    "                    st.append(node.left)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        data = []\n",
    "\n",
    "        def collect(node: TreeNode):\n",
    "            if not node:\n",
    "                return\n",
    "            data.append(str(node.val))\n",
    "            if  node.left:\n",
    "                data.append('(')\n",
    "                collect(node.left)\n",
    "                data.append(')')\n",
    "\n",
    "            if  node.right:\n",
    "                if not node.left:\n",
    "                    data.append('()')\n",
    "                data.append('(')\n",
    "                collect(node.right)\n",
    "                data.append(')')\n",
    "\n",
    "        collect(root)\n",
    "        return ''.join(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        ans = \"\"\n",
    "        st = [root]\n",
    "        vis = set()\n",
    "        while st:\n",
    "            node = st[-1]\n",
    "            if node in vis:\n",
    "                if node != root:\n",
    "                    ans += \")\"\n",
    "                st.pop()\n",
    "            else:\n",
    "                vis.add(node)\n",
    "                if node != root:\n",
    "                    ans += \"(\"\n",
    "                ans += str(node.val)\n",
    "                if node.left is None and node.right:\n",
    "                    ans += \"()\"\n",
    "                if node.right:\n",
    "                    st.append(node.right)\n",
    "                if node.left:\n",
    "                    st.append(node.left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        ans=''\n",
    "        stack=[root]\n",
    "        visited=set()\n",
    "        while stack:\n",
    "            node=stack[-1]\n",
    "            if node in visited:\n",
    "                if node!=root:\n",
    "                    ans+=')'\n",
    "                stack.pop()\n",
    "            else:\n",
    "                visited.add(node)\n",
    "                if node!=root:\n",
    "                    ans+='('\n",
    "                ans+=str(node.val)\n",
    "                if not node.left and node.right:\n",
    "                    ans+='()'\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "                if node.left:\n",
    "                    stack.append(node.left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        def traversal(root):\n",
    "            if not root:\n",
    "                return ''\n",
    "            if root.right:\n",
    "                left = traversal(root.left)\n",
    "                right = traversal(root.right)\n",
    "                return '{}({})({})'.format(root.val, left, right)\n",
    "            elif root.left:\n",
    "                left = traversal(root.left)\n",
    "                return '{}({})'.format(root.val, left)\n",
    "            else:\n",
    "                return '{}'.format(root.val)\n",
    "            \n",
    "\n",
    "        return traversal(root)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        if not root: return ''\n",
    "\n",
    "        left_res = '({})'.format(self.tree2str(root.left))  if (root.left or root.right) else ''\n",
    "        right_res = '({})'.format(self.tree2str(root.right))  if root.right else ''\n",
    "        return '{}{}{}'.format(root.val, left_res, right_res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "\n",
    "        def preOrder(node):\n",
    "            if node == None:\n",
    "                return None\n",
    "            else:\n",
    "                res= []\n",
    "                res.append(node.val)\n",
    "                if node.left != None and node.right != None:\n",
    "                    res.append(preOrder(node.left))\n",
    "                    res.append(preOrder(node.right))\n",
    "                elif  node.left != None and node.right == None:\n",
    "                    res.append(preOrder(node.left))\n",
    "                elif node.left == None and node.right != None:\n",
    "                    res.append(None)\n",
    "                    res.append(preOrder(node.right))\n",
    "\n",
    "                    \n",
    "                return res\n",
    "\n",
    "        a = preOrder(root)\n",
    "        c = str(a)\n",
    "        b = list(c)\n",
    "        i = 0\n",
    "        while i < len(b):\n",
    "            if b[i] == ' ':\n",
    "                b.pop(i)\n",
    "            elif b[i] == ',':\n",
    "                b.pop(i)\n",
    "            elif b[i] == 'N':\n",
    "                b.pop(i)\n",
    "                b.pop(i)\n",
    "                b.pop(i)\n",
    "                b[i] = '()'\n",
    "            else:\n",
    "                i += 1\n",
    "\n",
    "        for i in range(len(b)):\n",
    "            if b[i] == '[':\n",
    "                b[i] = '('\n",
    "            elif b[i] == ']':\n",
    "                b[i] = ')'\n",
    "\n",
    "        d = ''.join(b)\n",
    "        return d[1:-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "def treestr(self):\n",
    "    if self.left:\n",
    "        leftstr = f'({self.left})'\n",
    "        rightstr = f'({self.right})' if self.right else ''\n",
    "    elif self.right:\n",
    "        leftstr = '()'\n",
    "        rightstr = f'({self.right})'\n",
    "    else:\n",
    "        return str(self.val)\n",
    "    return f\"{self.val}{leftstr}{rightstr}\"\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        TreeNode.__str__ = treestr\n",
    "        return str(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = \"\"\n",
    "\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        self.recur(root)\n",
    "        return self.res\n",
    "    \n",
    "    def recur(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.res += str(root.val)\n",
    "        if not root.left and not root.right:\n",
    "            return\n",
    "        if root.left:\n",
    "            self.res += \"(\"\n",
    "            self.tree2str(root.left)\n",
    "            self.res += \")\"\n",
    "        else:\n",
    "            self.res += \"()\"\n",
    "        if root.right:\n",
    "            self.res += \"(\"\n",
    "            self.tree2str(root.right)\n",
    "            self.res += \")\"\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "\n",
    "        def preOrder(node):\n",
    "            if node == None:\n",
    "                return None\n",
    "            else:\n",
    "                res= []\n",
    "                res.append(node.val)\n",
    "                if node.left != None and node.right != None:\n",
    "                    res.append(preOrder(node.left))\n",
    "                    res.append(preOrder(node.right))\n",
    "                elif  node.left != None and node.right == None:\n",
    "                    res.append(preOrder(node.left))\n",
    "                elif node.left == None and node.right != None:\n",
    "                    res.append(None)\n",
    "                    res.append(preOrder(node.right))\n",
    "\n",
    "                    \n",
    "                return res\n",
    "\n",
    "        a = preOrder(root)\n",
    "        c = str(a)\n",
    "        b = list(c)\n",
    "        i = 0\n",
    "        while i < len(b):\n",
    "            if b[i] == ' ':\n",
    "                b.pop(i)\n",
    "            elif b[i] == ',':\n",
    "                b.pop(i)\n",
    "            elif b[i] == 'N':\n",
    "                b.pop(i)\n",
    "                b.pop(i)\n",
    "                b.pop(i)\n",
    "                b[i] = '()'\n",
    "            else:\n",
    "                i += 1\n",
    "\n",
    "        for i in range(len(b)):\n",
    "            if b[i] == '[':\n",
    "                b[i] = '('\n",
    "            elif b[i] == ']':\n",
    "                b[i] = ')'\n",
    "\n",
    "        d = ''.join(b)\n",
    "        return d[1:-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "\n",
    "        def preOrder(node):\n",
    "            if node == None:\n",
    "                return None\n",
    "            else:\n",
    "                res= []\n",
    "                res.append(node.val)\n",
    "                if node.left != None and node.right != None:\n",
    "                    res.append(preOrder(node.left))\n",
    "                    res.append(preOrder(node.right))\n",
    "                elif  node.left != None and node.right == None:\n",
    "                    res.append(preOrder(node.left))\n",
    "                elif node.left == None and node.right != None:\n",
    "                    res.append(None)\n",
    "                    res.append(preOrder(node.right))\n",
    "\n",
    "                    \n",
    "                return res\n",
    "\n",
    "        a = preOrder(root)\n",
    "        c = str(a)\n",
    "        b = list(c)\n",
    "        i = 0\n",
    "        while i < len(b):\n",
    "            if b[i] == ' ':\n",
    "                b.pop(i)\n",
    "            elif b[i] == ',':\n",
    "                b.pop(i)\n",
    "            elif b[i] == 'N':\n",
    "                b.pop(i)\n",
    "                b.pop(i)\n",
    "                b.pop(i)\n",
    "                b[i] = '()'\n",
    "            else:\n",
    "                i += 1\n",
    "\n",
    "        for i in range(len(b)):\n",
    "            if b[i] == '[':\n",
    "                b[i] = '('\n",
    "            elif b[i] == ']':\n",
    "                b[i] = ')'\n",
    "\n",
    "        d = ''.join(b)\n",
    "        return d[1:-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def tree2str(self, t: TreeNode) -> str:\n",
    "        def per(t):\n",
    "            if t == None:\n",
    "                return ''\n",
    "\n",
    "            result = str(t.val) + ''\n",
    "            if t.left != None or t.right != None:\n",
    "                result = result + '(' + self.tree2str(t.left) + ')'\n",
    "\n",
    "            if t.right != None:\n",
    "                result = result + '(' + self.tree2str(t.right) + ')'\n",
    "            return result\n",
    "        return per(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def tree2str(self, t: TreeNode) -> str:\n",
    "        def per(t):\n",
    "            if t == None:\n",
    "                return ''\n",
    "\n",
    "            result = str(t.val) + ''\n",
    "            if t.left != None or t.right != None:\n",
    "                result = result + '(' + self.tree2str(t.left) + ')'\n",
    "\n",
    "            if t.right != None:\n",
    "                result = result + '(' + self.tree2str(t.right) + ')'\n",
    "            return result\n",
    "        return per(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        if not root:\n",
    "            return ''\n",
    "        res=str(root.val)\n",
    "        if not root.left and not root.right:\n",
    "            return res\n",
    "        \n",
    "        leftstr=self.tree2str(root.left)\n",
    "        rightstr=self.tree2str(root.right)\n",
    "        \n",
    "        res=res + '(' + leftstr + ')'\n",
    "        if  rightstr:\n",
    "            res+='('+rightstr+')'\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, t: TreeNode) -> str:\n",
    "        if not t:\n",
    "            return ''\n",
    "        left = '('+self.tree2str(t.left)+')' if (t.left or t.right) else ''\n",
    "        right = '('+self.tree2str(t.right)+')' if t.right else ''\n",
    "        return str(t.val) +left + right\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        if root.left is None and root.right is None:\n",
    "            return str(root.val)\n",
    "        if root.right is None:\n",
    "            return f\"{root.val}({self.tree2str(root.left)})\"\n",
    "        \n",
    "        return f\"{root.val}({self.tree2str(root.left)})({self.tree2str(root.right)})\"\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        if root is None:\n",
    "            return \"\"\n",
    "        if root.left is None and root.right is None:\n",
    "            return str(root.val)\n",
    "        if root.right is None:\n",
    "            return f\"{root.val}({self.tree2str(root.left)})\"\n",
    "        return f\"{root.val}({self.tree2str(root.left)})({self.tree2str(root.right)})\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        # def genStr(a):\n",
    "        #     if not a.left and not a.right:\n",
    "        #         return str(a.val)\n",
    "        #     if not a.left:\n",
    "        #         return str(a.val)+'()('+genStr(a.right)+')'\n",
    "        #     if not a.right:\n",
    "        #         return str(a.val)+'('+genStr(a.left)+')'\n",
    "        #     return str(a.val)+'('+genStr(a.left)+')('+genStr(a.right)+')'\n",
    "\n",
    "        if not root.left and not root.right:\n",
    "            return str(root.val)\n",
    "        if not root.left:\n",
    "            return str(root.val)+'()('+self.tree2str(root.right)+')'\n",
    "        if not root.right:\n",
    "            return str(root.val)+'('+self.tree2str(root.left)+')'\n",
    "        return str(root.val)+'('+self.tree2str(root.left)+')('+self.tree2str(root.right)+')'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = rightclass\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: TreeNode) -> str:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return '()'\n",
    "        \n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "            \n",
    "            if left == right == '()':\n",
    "                return '(' + str(root.val) + ')'\n",
    "            elif left != '()' and right == '()':\n",
    "                return '(' + str(root.val) + left + ')'\n",
    "            #elif right != '()' and left == '()':\n",
    "                #return '(' + str(root.val) + right + ')'\n",
    "            else:\n",
    "                return '(' + str(root.val) + left + right + ')'\n",
    "\n",
    "        return dfs(root)[1:-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        if root is None:\n",
    "            return \"\"\n",
    "        if root.left is None and root.right is None:\n",
    "            return str(root.val)\n",
    "        if root.right is None:\n",
    "            return f\"{root.val}({self.tree2str(root.left)})\"\n",
    "        return f\"{root.val}({self.tree2str(root.left)})({self.tree2str(root.right)})\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        if root is None:\n",
    "            return ''\n",
    "\n",
    "        l_str = '' if root.left is None else self.tree2str(root.left)\n",
    "        r_str = '' if root.right is None else self.tree2str(root.right)\n",
    "        result = ''\n",
    "        if l_str != '' and r_str != '':\n",
    "            result = '(' + l_str + ')' + '(' + r_str + ')'\n",
    "        elif l_str != '':\n",
    "            result = '(' + l_str + ')'\n",
    "        elif r_str != '':\n",
    "            result = '()(' + r_str + ')'\n",
    "        return str(root.val) + result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        def func(node):\n",
    "            if not node.left and not node.right:\n",
    "                return str(node.val)\n",
    "            elif not node.left and node.right:\n",
    "                return str(node.val) + '()(' + func(node.right) + ')'\n",
    "            elif node.left and not node.right:\n",
    "                return str(node.val) + '(' + func(node.left) + ')'\n",
    "            else:\n",
    "                return str(node.val) + '(' + func(node.left) + ')' + '(' + func(node.right) + ')'\n",
    "        \n",
    "        return func(root)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        self.res = \"\"\n",
    "        self.PreTraverse(root)\n",
    "        return self.res\n",
    "    \n",
    "    def PreTraverse(self,root):\n",
    "        if root:\n",
    "            self.res += str(root.val)\n",
    "            self.res += \"(\"\n",
    "            l = self.PreTraverse(root.left)\n",
    "            self.res += \")(\"\n",
    "            r = self.PreTraverse(root.right)\n",
    "            self.res += \")\"\n",
    "            if l == \"no\" and r == \"no\":\n",
    "                self.res = self.res[:-4:1]\n",
    "            elif l != \"no\" and r == \"no\":\n",
    "                self.res = self.res[:-2:1]\n",
    "        else:\n",
    "            return \"no\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        self.res = \"\"\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        def traverse(node):\n",
    "            if node.val is None:\n",
    "                return\n",
    "            self.res += str(node.val) \n",
    "            if node.left is not None:\n",
    "                self.res += \"(\"\n",
    "                traverse(node.left)\n",
    "            if node.left is None and node.right is not None:\n",
    "                self.res += \"()\"\n",
    "            if node.right is not None:\n",
    "                self.res += \"(\"\n",
    "                traverse(node.right)\n",
    "            self.res += \")\"\n",
    "        traverse(root)\n",
    "        return self.res[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        res = \"\"\n",
    "        self.PreTraverse(root,res)\n",
    "        return self.PreTraverse(root,res)\n",
    "    \n",
    "    def PreTraverse(self,root,res):\n",
    "        if not root:\n",
    "            return ''\n",
    "        res = str(root.val)\n",
    "        if not root.left and not root.right:\n",
    "            return res\n",
    "        l = self.PreTraverse(root.left,res)\n",
    "        r = self.PreTraverse(root.right,res)\n",
    "        res += '(' + l + ')'\n",
    "        if r:\n",
    "            res += '(' + r + ')'\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return ''\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            res = ''\n",
    "            if left and not right:\n",
    "                res = '(' + left + ')' + right\n",
    "            if not left and right:\n",
    "                res = '()' + '(' + right + ')'\n",
    "            if left and right:\n",
    "                res = '(' + left + ')' + '(' + right + ')'\n",
    "            return str(node.val) + res\n",
    "        res = dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.answer = \"\"\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        if not root:\n",
    "            self.answer += \"()\"\n",
    "            return None\n",
    "        if not root.left and not root.right:\n",
    "            self.answer += \"({})\".format(root.val)\n",
    "            return self.answer[1:-1]\n",
    "        \n",
    "        self.answer += \"({}\".format(root.val)\n",
    "        if root.left and not root.right:\n",
    "            self.tree2str(root.left)\n",
    "        else:\n",
    "            self.tree2str(root.left)\n",
    "            self.tree2str(root.right)\n",
    "        self.answer += \")\"\n",
    "\n",
    "        return self.answer[1:-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        if root is None:\n",
    "            return \"\"\n",
    "        if root.left is None and root.right is None:\n",
    "            return str(root.val)\n",
    "        if root.right is None:\n",
    "            return f\"{root.val}({self.tree2str(root.left)})\"\n",
    "        return f\"{root.val}({self.tree2str(root.left)})({self.tree2str(root.right)})\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        return self.get_str(root)\n",
    "        # res = ''\n",
    "        # l = s.split('()')\n",
    "        # for char in l:\n",
    "        #     res += char\n",
    "        # return res\n",
    "\n",
    "    def get_str(self, root):\n",
    "        if not root:\n",
    "            return ''\n",
    "        if not root.left and not root.right:\n",
    "            return f'{root.val}'\n",
    "        else:\n",
    "            return f'{root.val}' + self.dbs(root.left, 'left') + self.dbs(root.right, 'right')\n",
    "\n",
    "    def dbs(self, root, flag='left'):\n",
    "        if not root:\n",
    "            if flag == 'left':\n",
    "                return '()'\n",
    "            else:\n",
    "                return ''\n",
    "        if not root.left and not root.right:\n",
    "            return f'({root.val})'\n",
    "        else:\n",
    "            return '(' + f'{root.val}' + self.dbs(root.left, 'left') + self.dbs(root.right, 'right') + ')'\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        res=[]\n",
    "        def dfs(root,res):\n",
    "            if not root: return\n",
    "            res.append(str(root.val))\n",
    "            dfs(root.left,res+['('])\n",
    "            dfs(root.right,res+[')'])\n",
    "        dfs(root,res)\n",
    "        return \"\".join(res)\n",
    "\n",
    "class Solution:\n",
    "    def tree2str(self, root: TreeNode) -> str:\n",
    "        # 前序遍历\n",
    "        def dfs(root): \n",
    "            if not root: return\n",
    "            elif not root.left and not root.right:\n",
    "                return str(root.val)\n",
    "            elif not root.left and root.right:\n",
    "                return str(root.val) + \"()\" + \"(\" + dfs(root.right) +\")\"\n",
    "            elif root.left and not root.right:\n",
    "                return str(root.val) + \"(\" + dfs(root.left) +\")\"\n",
    "            elif root.left and root.right:\n",
    "                return str(root.val)  + \"(\" + dfs(root.left) +\")\" + \"(\" + dfs(root.right) +\")\"\n",
    "        return dfs(root)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        self.res = \"\"\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        def traverse(node):\n",
    "            if node.val is None:\n",
    "                return\n",
    "            self.res += str(node.val) \n",
    "            if node.left is not None:\n",
    "                self.res += \"(\"\n",
    "                traverse(node.left)\n",
    "            if node.left is None and node.right is not None:\n",
    "                self.res += \"()\"\n",
    "            if node.right is not None:\n",
    "                self.res += \"(\"\n",
    "                traverse(node.right)\n",
    "            self.res += \")\"\n",
    "        traverse(root)\n",
    "        return self.res[:-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        if root is None:\n",
    "            return \"\"\n",
    "        r = f\"{root.val}\"\n",
    "        L = self.tree2str(root.left)\n",
    "        R = self.tree2str(root.right)\n",
    "        if len(L) > 0 and len(R) > 0:\n",
    "            r = f\"{r}({L})({R})\"\n",
    "        elif len(L) > 0:\n",
    "            r = f\"{r}({L})\"\n",
    "        elif len(R) > 0:\n",
    "            r = f\"{r}()({R})\"\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        if not root:\n",
    "            return ''\n",
    "        \n",
    "        if not root.left and not root.right:\n",
    "            return str(root.val)\n",
    "        if not root.right:\n",
    "            return f'{root.val}({self.tree2str(root.left)})'\n",
    "        else:\n",
    "            return f'{root.val}({self.tree2str(root.left)})({self.tree2str(root.right)})'\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        self.res = \"\"\n",
    "        self.PreTraverse(root)\n",
    "        return self.res\n",
    "    \n",
    "    def PreTraverse(self,root):\n",
    "        if root:\n",
    "            self.res += str(root.val)\n",
    "            self.res += \"(\"\n",
    "            self.PreTraverse(root.left)\n",
    "            self.res += \")(\"\n",
    "            self.PreTraverse(root.right)\n",
    "            self.res += \")\"\n",
    "            if not root.left and not root.right:\n",
    "                self.res = self.res[:-4:1]\n",
    "            elif root.left and  not root.right:\n",
    "                self.res = self.res[:-2:1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        def recur(root):\n",
    "            if not root:\n",
    "                return ''\n",
    "            sl=recur(root.left)\n",
    "            sr=recur(root.right)\n",
    "            if sr!='':\n",
    "                sl='('+sl+')'\n",
    "                sr='('+sr+')'\n",
    "            elif sl!='':\n",
    "                sl='('+sl+')'\n",
    "            return str(root.val)+sl+sr\n",
    "\n",
    "        return recur(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        self.res = \"\"\n",
    "        self.PreTraverse(root)\n",
    "        return self.res\n",
    "    \n",
    "    def PreTraverse(self,root):\n",
    "        if root:\n",
    "            self.res += str(root.val)\n",
    "            self.res += \"(\"\n",
    "            self.PreTraverse(root.left)\n",
    "            self.res += \")(\"\n",
    "            self.PreTraverse(root.right)\n",
    "            self.res += \")\"\n",
    "            if not root.left and not root.right:\n",
    "                self.res = self.res[:-4:1]\n",
    "            elif root.left and  not root.right:\n",
    "                self.res = self.res[:-2:1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        def recur(root):\n",
    "            if not root:\n",
    "                return ''\n",
    "            sl=recur(root.left)\n",
    "            sr=recur(root.right)\n",
    "            if sr!='':\n",
    "                sl='('+sl+')'\n",
    "                sr='('+sr+')'\n",
    "            elif sl!='':\n",
    "                sl='('+sl+')'\n",
    "            return str(root.val)+sl+sr\n",
    "\n",
    "        return recur(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        self.res = \"\"\n",
    "        self.PreTraverse(root)\n",
    "        return self.res\n",
    "    \n",
    "    def PreTraverse(self,root):\n",
    "        if root:\n",
    "            self.res += str(root.val)\n",
    "            self.res += \"(\"\n",
    "            l = self.PreTraverse(root.left)\n",
    "            self.res += \")(\"\n",
    "            r = self.PreTraverse(root.right)\n",
    "            self.res += \")\"\n",
    "            if l == \"no\" and r == \"no\":\n",
    "                self.res = self.res.replace(\"()()\",\"\")\n",
    "            elif l != \"no\" and r == \"no\":\n",
    "                if self.res.count(\"()\") == 1:\n",
    "                    self.res = self.res.replace(\"()\",\"\")\n",
    "                else:\n",
    "                    self.res = self.res[:-2:1]\n",
    "        else:\n",
    "            return \"no\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        visit = []\n",
    "        def travse(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            visit.append(\"(\")\n",
    "            visit.append(str(root.val))\n",
    "            if root.left:\n",
    "                travse(root.left)\n",
    "            if not root.left and root.right:\n",
    "                visit.append(\"()\")\n",
    "            if root.right:\n",
    "                travse(root.right)\n",
    "            \n",
    "            visit.append(\")\")\n",
    "        travse(root)\n",
    "        ans = ''.join(visit[1:-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        if root is None:\n",
    "            return '()'\n",
    "        \n",
    "        left = self.tree2str(root.left)\n",
    "        right = self.tree2str(root.right)\n",
    "        if root.left is not None and root.right is not None:\n",
    "            return f'{root.val}({left})({right})'\n",
    "        elif root.left is not None and root.right is None:\n",
    "            return f'{root.val}({left})'\n",
    "        elif root.left is None and root.right is not None:\n",
    "            return f'{root.val}()({right})'\n",
    "        else:\n",
    "            return str(root.val)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        if root is None:\n",
    "            return \"\"\n",
    "        if root.left is None and root.right is None:\n",
    "            return str(root.val)\n",
    "        if root.right is None:\n",
    "            return f\"{root.val}({self.tree2str(root.left)})\"\n",
    "        return f\"{root.val}({self.tree2str(root.left)})({self.tree2str(root.right)})\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        if not root: return ''\n",
    "\n",
    "        left_res = '({})'.format(self.tree2str(root.left)) if (root.left or root.right) else ''\n",
    "        right_res = '({})'.format(self.tree2str(root.right)) if root.right else ''\n",
    "        return '{}{}{}'.format(root.val, left_res, right_res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        \n",
    "        if not root:\n",
    "            return ''\n",
    "        if not root.right and root.left:\n",
    "            return ''.join([str(root.val),'(',self.tree2str(root.left),')']) \n",
    "        if not root.left and not root.right:\n",
    "            return str(root.val)\n",
    "        return ''.join([str(root.val),'(',self.tree2str(root.left),')','(',self.tree2str(root.right),')']) \n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        \n",
    "        if not root:\n",
    "            return ''\n",
    "        if not root.right and root.left:\n",
    "            return f\"{str(root.val)}({self.tree2str(root.left)})\"\n",
    "        if not root.left and not root.right:\n",
    "            return str(root.val)\n",
    "        return ''.join([str(root.val),'(',self.tree2str(root.left),')','(',self.tree2str(root.right),')']) \n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        if root is None:\n",
    "            return '()'\n",
    "        \n",
    "        left = self.tree2str(root.left)\n",
    "        right = self.tree2str(root.right)\n",
    "        if root.left is not None and root.right is not None:\n",
    "            return f'{root.val}({left})({right})'\n",
    "        elif root.left is not None and root.right is None:\n",
    "            return f'{root.val}({left})'\n",
    "        elif root.left is None and root.right is not None:\n",
    "            return f'{root.val}()({right})'\n",
    "        else:\n",
    "            return str(root.val)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "        if root is None:\n",
    "            return ''\n",
    "        if root.left is None and root.right is None:\n",
    "            return str(root.val)\n",
    "        if root.right is None:\n",
    "            return '{}({})'.format(root.val, self.tree2str(root.left))\n",
    "        return '{}({})({})'.format(root.val, self.tree2str(root.left), self.tree2str(root.right))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree2str(self, root: Optional[TreeNode]) -> str:\n",
    "\n",
    "        \"\"\"\n",
    "        給一個 binary tree 的 root\n",
    "        使用 preorder traversal 的方式建立出一個由括號和整數組成的字串\n",
    "        note. 排除 \"空的括號\", 但是要保持 input 和 output string 的一致性\n",
    "        \"\"\"\n",
    "\n",
    "        result = []\n",
    "\n",
    "        def preorder(node):\n",
    "            if not node: return\n",
    "            \n",
    "            result.append(str(node.val))\n",
    "\n",
    "            if node.left:\n",
    "                result.append(\"(\")\n",
    "                preorder(node.left)\n",
    "                result.append(\")\")\n",
    "\n",
    "            if node.right:\n",
    "                if not node.left:\n",
    "                    result.append(\"(\")\n",
    "                    result.append(\")\")\n",
    "                \n",
    "                result.append(\"(\")\n",
    "                preorder(node.right)\n",
    "                result.append(\")\")\n",
    "                \n",
    "        preorder(root)\n",
    "        return \"\".join(result)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
